Attribute VB_Name = "modQSortUnsigned"
'***************************************************************
' (c) Copyright 2000 Matthew J. Curland
'
' This file is from the CD-ROM accompanying the book:
' Advanced Visual Basic 6: Power Techniques for Everyday Programs
'   Author: Matthew Curland
'   Published by: Addison-Wesley, July 2000
'   ISBN: 0-201-70712-8
'   http://www.PowerVB.com
'
' You are entitled to license free distribution of any application
'   that uses this file if you own a copy of the book, or if you
'   have obtained the file from a source approved by the author. You
'   may redistribute this file only with express written permission
'   of the author.
'
' This file depends on:
'   References:
'     VBoostTypes6.olb (VBoost Object Types (6.0))
'   VBoost6.Dll (VBoost Object Implementation (6.0)) (optional)
'     Compare.tlb (VBoost: Compare declaration for qsort and bsearch)
'   Files:
'     FunctionDelegator.bas
'     StackAlloc.bas
'     StackFree.bas
'   Minimal VBoost conditionals:
'     VBOOST_INTERNAL = 1 : VBOOST_CUSTOM = 1
'   Conditional Compilation Values:
'     FUNCTIONDELEGATOR_NOHEAP = 1 'Minimize FunctionDelegator impact
'
' This file is discussed in Chapter 11.
'***************************************************************
Option Explicit

'Pass a structure to the recursive QuickSortInternal
'function to minimize stack usage
Private Type QuickSortData
    Size As Long
    Compare As ICallCompare
    pBytes As Long
End Type

Public Sub QuickSort(ByVal pBase As Long, ByVal Number As Long, ByVal Size As Long, ByVal pfCompare As Long)
Dim Data As QuickSortData
Dim FDCompare As FunctionDelegator
Dim cBytes As Long
    With Data
        .Size = Size
        Set .Compare = InitDelegator(FDCompare, pfCompare)
        cBytes = AlignedSize(Size)
        .pBytes = StackAlloc.Call(cBytes)
        On Error GoTo Error
        QuickSortInternal pBase, _
          VBoost.UAdd(pBase, (Number - 1) * Size), Data
    End With
    If cBytes Then StackFree.Call cBytes
    Exit Sub
Error:
    With Err
        .Raise .Number, .Source, .Description, .HelpFile, .HelpContext
    End With
End Sub

Private Sub QuickSortInternal(ByVal Low As Long, ByVal High As Long, Data As QuickSortData)
Dim PivotIndex As Long
Dim i As Long, j As Long
    With VBoost
        If Low < High Then
            ' Only two elements in this subdivision; swap them if they are out of
            ' order, then end recursive calls:
            If VBoost.UDif(High, Low) = Data.Size Then
                If Data.Compare.Compare(Low, High) > 0 Then
                    SwapBytes Low, High, Data
                End If
            Else
                ' Pick a pivot element in the middle, then move it to the end:
                PivotIndex = VBoost.UAdd(VBoost.UDiv(Low, 2), VBoost.UDiv(High, 2)) 'Don't use (Low + High) \ 2, it can overflow
                PivotIndex = VBoost.UDif(PivotIndex, VBoost.UDif(PivotIndex, Low) Mod Data.Size) 'Align on m_Size boundary
                SwapBytes High, PivotIndex, Data
                ' Move in from both sides towards the pivot element:
                i = Low: j = High
                Do
                    Do While (VBoost.UGT(j, i)) And (Data.Compare.Compare(i, High) <= 0)
                       i = VBoost.UAdd(i, Data.Size)
                    Loop
                    Do While (VBoost.UGT(j, i)) And (Data.Compare.Compare(j, High) >= 0)
                       j = VBoost.UDif(j, Data.Size)
                    Loop
                    
                    ' If we haven't reached the pivot element, it means that two
                    ' elements on either side are out of order, so swap them:
                    If VBoost.UGT(j, i) Then
                       SwapBytes i, j, Data
                    End If
                Loop While VBoost.UGT(j, i)
                
                ' Move the pivot element back to its proper place in the array:
                SwapBytes i, High, Data
                
                ' Recursively call the QuickSort procedure (pass the smaller
                ' subdivision first to use less stack space):
                If VBoost.UGT(VBoost.UDif(High, i), VBoost.UDif(i, Low)) Then
                    QuickSortInternal Low, VBoost.UDif(i, Data.Size), Data
                    QuickSortInternal VBoost.UAdd(i, Data.Size), High, Data
                Else
                    QuickSortInternal VBoost.UAdd(i, Data.Size), High, Data
                    QuickSortInternal Low, VBoost.UDif(i, Data.Size), Data
                End If
            End If
        End If
    End With
End Sub

Private Sub SwapBytes(ByVal pElem1 As Long, ByVal pElem2 As Long, Data As QuickSortData)
    With Data
        CopyMemory ByVal .pBytes, ByVal pElem1, .Size
        CopyMemory ByVal pElem1, ByVal pElem2, .Size
        CopyMemory ByVal pElem2, ByVal .pBytes, .Size
    End With
End Sub



